package com.leetcode.offer.chapter5;

/**
 * @author Dennis Li
 * @date 2020/7/15 17:54
 */
public class MissingNumber_53 {

    // 纯遍历
    public int missingNumber(int[] nums) {
        for (int i = 0; i < nums.length; i++)
            if (nums[i] != i) return i;
        return nums.length;
    }

    // 二分
    // 这道题二分的关键点在于判断左右两部分，相加是否恰好为中间序号
    public int missingNumber2(int[] nums) {
        int i = 0, j = nums.length - 1;
        while (i <= j) {
            int mid = (i + j) >> 1;
            // 中位数等于nums[mid] 说明在右边
            if (nums[mid] == mid) i = mid + 1;
            // 否则在左边
            else j = mid - 1;
        }
        return i;
    }

}
